/*实验二 单链表及其应用
线性表及其所有操作也可以使用单链表来实现。单链表由一系列不必在内存中连续的结点组成，每一个结点均含有一个表元素和指向包含该元素后继元的结点的指针链。本实验实现单链表和它的一些相关应用。
（1）实验目的
（1）掌握单链表的组织结构；
（2）掌握单链表的基本操作：插入、删除、读取、查找等；
（3）掌握上机调试单链表的基本方法。
（2）实验内容
（1）单链表的实现
目标：定义一个可存放整型数据的单链表，并实现其常用算法。
（1）算法填空：根据功能提示，完善下划线处的代码。
（1）单链表节点的定义
定义相应的结构体数据类型，用来表示单链表中的一个数据节点。*/
/*链表(基于指针)的数据结构基于单个元素,而顺序表的数据结构式基于整个表*/
#define _CRT_SECURE_NO_WARNINGS
#define   ERROR   -999999
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
#define MAXLEN 100
/*链表的普通结构*/
typedef struct node {
	int data;   // 用来存放节点中的数据元素
	struct node* link;  // 指向后继节点的指针链：表尾结点的后继结点为空
}LNode;/*无法直接在内部用NODE来代替struct node*/
/*链表的多项式的结点结构
typedef struct PloyNode
{
	int exp;
	int coef;
	PloyNode* next;
}Poly;*/


/*（2）初始化单链表(头结点)
在使用单链表之前，初始化其为一个带头结点的空链表。
可以通过一个函数实现该操作，函数返回空链表中头结点的地址。*/
LNode* InitList()
{
	/**********************************************************
	初始化一个单链表：构建一个带头结点的空链表
	*********************************************************/
	/*为什么要malloc内存来构建结点?因为malloc来的内存除非被free(),否则可以长期存在,这样通过函数内部创建的结点就可以在函数之外访问*/
	LNode* pHead = (LNode*)malloc(sizeof(LNode)); // 分配头结点内存(此块内存被强制转化为保存LNode型变量)
	/*需要注意的是,pHead保存的是(某块内存的)地址,是LNode类型的指针,而非LNode型变量本身
	变量：用来标识一块内存区域，即
	变量就是一块内存区域，而这个区域里面的值可以更改，故叫做‘变’量
变量名：是一个标识符，用来指代一块内存区域，即变量，变量名并不占用内存空间，使用变量名让我们操作内存以区域、以块为单位，提高了方便性*/
	if (!pHead)
	{
		printf("malloc failed.\n");
		exit(1);
	}
	pHead->data = ERROR;
	pHead->link = NULL;  // 设置头结点的后继结点为空：空链表

	return pHead;/*返回局部变量pHead的值本身*/
}
/*3）插入元素
在单链表的某一元素位置 之前 插入一个新元素(其实就是在这个位置上插入元素,旧有的元素往后移)
插入位置的允许范围为[1, n + 1]，n为当前的表长。
当插入位置为n + 1时，表示在表尾插入。
*/
int InsertList(LNode* pHead, int i, int x)
{
	/**********************************************************
	在pHead指向的单链表的 第i个位置之前插入值为x的新元素(而一般是先找到 i-1 处,因为要在第i-1与第i个节点之间插入)
	*********************************************************/
	LNode* q = 0,/* q用来保存新申请的结点的内存地址.
	这里比较特殊,只允许0这个特殊整数(NULL)赋值给指针*/
		* p = pHead;/* p用来遍历链表中的元素直到找到目标位置为止.找到表中的第i-1个数据节点
		初始化insertp*/
	int j = 0;/*记录当前抵达的位置*/

	/*  1. 通过指针p，遍历表中元素，
	找到表中的第i-1个数据节点(因为要在第i-1与第i个节点之间，把新节点放入到单链表中)
		 注意：必须保证p不超出表的范围
		 不是直接找第i个位置,要先找目标位置i的前一个位置,需要两个位置的辅助指针才能完成插入. */
		 /*找到位置*/
	while (p != NULL && j < i - 1) {/*为了更准确的理解语句,可以让i取得两个特殊值来验证想法);以及
									 最后一次进入循环j的取值情况;离开循环时j的取值*/
									 /*j < i - 1 表示还未抵达第i个位置;同时还要求链表有足够多的元素可以前进第i个位置(p != NULL)可以直接简写为p */
		p = p->link;
		j++;/*记录前进程度,注意j的自增发生在p前进一步之后(实际上while内部的这两条语句顺序任意,因为
			两条语句相互独立,执行其中的任意一条,另一条必定也会执行,否则就都不执行.明白这一点时重要的.*/
	}

	if (j != i - 1) {
		// 表中不存在第i-1个节点，表明插入位置非法(在找到i位置之前就没有元素了(也可用j< i - 1 或 !p 来判断)
		return -1;
	}/*如果完此执行判断,还可以继续,那么说明此时p就是指向第i个节点的指针. */

	// 2. 为新元素分配一个节点空间，并把元素存入该节点(的数据域)
	q = (LNode*)malloc(sizeof(LNode));
	q->data = x;

	// 3. 在第i-1与第i个节点之间，把新节点放入到单链表中， 
	q->link = p->link;/*p,q只是指针(地址)*/
	p->link = q;/*链表的链接一定要体现指针域*/

	return i; // 返回插入元素在表中的位置
}
/*（4）读取元素
读取单链表中某一位置处的元素。读取位置必须在表的长度范围之内，即[1, n]，n为当前的表长。*/
int GetList(LNode* pHead, int i)
{
	/**********************************************************
	读取pHead指向的单链表的第i个位置处的元素
	*********************************************************/
	// 1. 根据函数功能实现，定义相应的变量

	int j = 0;
	LNode* p = pHead;

	// 2. 通过一个指针，遍历表中元素，找到表中的第i个数据节点
   // 注意：遍历过程中，若指针超出表的范围，表明读取位置非法，可// 通过exit(0) 退出

		//while (p && )
	for (j = 0; j < i && p; j++)/*当i=1时,验证循环区间是否可以*/
	{
		p = p->link;
	}


	return p->data; 	// 返回第i个节点处的元素值
}
/*（5）调试
使用上述操作，完成下面代码，运行并调试程序。
*/
int DeleteList(LNode* pHead, int i);
int FindList(LNode* pHead, int x);
int LengthList(LNode* pHead);
void ClearList(LNode* pHead);
void InvertList(LNode* pHead);
LNode* AddPolynomial(LNode* poly1, LNode* poly2);

int main()
{
	LNode* pHead = 0;  // 定义一个单链表的头指针(初始化为空指针)

	// 1. 初始化该单链表(这里是得到一个由InitList()创建的头结点的地址) 
	pHead = InitList();

	// 2. 用户输入若干个整数，并依次插入到该单链表中
	printf("输入若干个整数(以-1表示结束):\n");
	int n = 0;
	int i = 0;
	while (scanf("%d", &n) && n != -1)
	{
		++i;
		InsertList(pHead, i, n);
	}
	/*调试函数:

	printf("测试GetList():\n");
	printf("第4个元素为:%d\n", GetList(pHead, 4));
*/
/*	printf("测试Deletelist(),输入:2\n");
	printf("第%d个元素被删除,(若返回-1表示删除失败).\n",DeleteList(pHead, 2));

	printf("测试Findlist()函数:输入3:\n");
	int x;
	printf("查找值为:\n");
	scanf("%d", &x);
	printf("值为%d的元素第一次出现在第:%d处(若返回-1表示删除失败)\n",x, FindList(pHead, x));

	printf("测试lenthList():\n");
	printf("当前链表长度为:%d\n", LengthList(pHead));

	printf("测试clearlist():\n");
	ClearList(pHead);
	printf("链表已清空\n");
*/
	printf("测试Invertlist():\n");
	InvertList(&pHead);

	// 3. 由前往后，依次读取并输出单链表中每个位置处的元素 
	printf("由前往后输出当前单链表中的元素\n");
	/*
	while (pHead->link)
	{
		pHead = pHead->link;
		printf("%d ", pHead->data);

	}*/

	/*专门打印逆序函数的操纵结果*/
	while (pHead->data!=ERROR)
	{
		printf("%d ", pHead->data);
		pHead = pHead->link;

	}

}
//（2）算法练习：根据功能提示，实现算法。
//（6）删除元素
//删除单链表中某一位置处的元素。待删除元素位置的允许范围为[1, n]，n为当前的表长。算法实现提示：
//1）在表中遍历到待删除元素位置的前驱节点；2）把待删除元素所在节点从表中移除，注意保持链表的完整性；
//3）释放待删除元素所在节点的内存，可通过free()函数实现。如删除失败，返回 - 1；否则返回删除位置。函数原型如下：
///**********************************************************
//删除pHead指向的单链表的第i个位置处的元素
//*********************************************************/
int DeleteList(LNode* pHead, int i)
{
	/*辅助指针是必须的,否则无法标识特定位置的结点
	(此外,对于单向的链表(单链表),一个辅助指针只可以标识本身所指结点以及后继结点,无法标识前驱结点.*/
	LNode* p, * q;
	int j = 0;
	/*删除链表的前提条件时判断链表是否为空
	if (pHead == NULL)
	{
		return 0;//结束函数
	}可以留到后面统一判断*/
	/*若链表非空,初始化辅助指针*/
	p = pHead; q = NULL;
	/*找到第i-1个元素*//*i的合法取值范围是[1,n](n为当前表长,但尚未知道为何值,表尾结点是最后一个合法的可删除的有元素结点)*/
	while (p->link && j < i - 1)/*p->link看成一个整体;先从合法的情况判断(链表够长,i也再合法范围内
							  着眼于离开循环时,指针与计数器的状态*/
							  /*跳出的可能性有p->link == NULL或仅j>=i-1,两种可能 */
	{
		p = p->link;
		j++;
	}/*若是由于p->link == NULL (此时j是表尾结点的所连的NULL的位置)i超过了表长n,而跳出,说明链表元素不足,发生越界.*/
	if (!(p->link) || j > i - 1)/*前者处理i过大(包括空表的情况);后者(j>i-1)处理i过小(i<1会更直接,前一种写法是由于while()里的对立事件
							)(0,-1,...)取i=0,i=1 分别从while开始测试 */
	{
		return -1;/*删除失败的出口*/
	}
	/*删除操作,画个示意图即可*/
	q = p->link;/*保存p->link*/
	p->link = q->link;/*再修改p->link*/
	free(q);/*链表的删除函数之所以在回到主函数时效果还在,正是由于调用了free()*/
	return j + 1;/*删除成功的出口*/

}
//（7）查找元素(不需要担心越界问题,从头找到尾即可)
//在单链表中查找与某给定值相等的元素。如找到，返回元素位置；否则，返回 - 1。函数原型如下：
///**********************************************************
//在pHead指向的单链表中查找值为x的元素
//*********************************************************/
int FindList(LNode* pHead, int x)
{
	LNode* p = pHead->link;/*Let p point to the first node element*/
	int j = 1;
	/*Look up the pointer until p is a null pointer or p points to the x-th(第x个元素) element*/
	while (p)
	{
		if (p->data == x)
		{
			return j;
		}
		p = p->link;
		j++;

	}
	return -1;


}
//（8）计算表长度
//计算单链表中的元素个数。函数原型如下：
///**********************************************************
//计算pHead指向的单链表中的元素个数
//*********************************************************/
int LengthList(LNode* pHead)/*本函数只要返回统计结果n,而不需要(也不会)实际地修改pHead(指离开该函数后pHead会发生变化)*/
{
	/*直接使用pHead作为辅助指针,在函数中变量phead值被修改,离开函数后phead还原为传入函数前的值(地址)(指针暂时指向其他地方)
	如果想要把修改的结果带出该函数,那么就要传入phead的指针(由于phead已经是一个指针变量,会变成二级指针的)  */
	int n = 0;
	while (pHead->link)
	{
		pHead = pHead->link;
		n++;
	}
	return n;
}

//（9）清空单链表
//当单链表不再使用时，需要释放其所有节点的内存，可通过如下函数实现：
///**********************************************************
//释放pHead指向的单链表中的所有节点（包括头结点）的内存(需要使用两个辅助指针,迭代进行)
//*********************************************************/
void ClearList(LNode* pHead)
{
	LNode* p = pHead, * q;/*p初始化为头结点,当然可以直接用pHead,但是为了可读性,在额外设立一个指针p代替*/
	/*开始释放(表头到表尾)*/
	while (p)
	{
		q = p->link;
		free(p);
		p = q;
	}

}
//（10）调试
//构建测试数据，在主函数中调用上述所有操作，运行并调试程序。

/*（3）思考
（1）双向链表
在单链表中，可快速访问到任意结点的后继节点，但是为了访问某一结点的前驱结点，
则需要从表头开始依次遍历。为了快速访问到任意结点的前驱节点，可在结点结构中增加一个指向前驱节点的指针链，
这时单链表即成为双向链表。尝试实现双向链表及其常用算法。
（2）循环链表
在单链表的表尾结点中，指向后继结点的指针链为空。如果把该指针链指向头结点，则单链表即成为循环链表。
这时，如何判断链表为空？如何计算链表中数据元素的个数？
尝试使用循环链表实现Josephi问题。
（2）单链表的应用
目标：灵活使用单链表，能够利用单链表解决一些实际应用问题。
*/
////（1）反转单链表
/*定义一个单链表，用户输入若干个整数并依次插入到该单链表中。

实现算法，按照结点连接次序反转单链表。最后，
依次读取并输出反转后的单链表中结点所包含的元素。
*/
/*反转单链表的算法可通过如下函数实现：
间接传参并不复杂,只需要在函数原型处再加个* ;而再调用该函数时再原本量前再加个&;函数内部将原变量前加*(建议用括号再引起来)
链表内部的修改一级指针以可以保留结果,但由于我们传入的时二级指针,故内部的表达式要稍作修改.*/
void InvertList(LNode** pHead)/*这个函数试图修改pHead的值,如果只用形参为(LNode*pHead),即参数为LNode型的一级指针的pHead的话,将无法修改pHead,
							  这就导致如果任然要使用pHead来指向新链表的表头,将无法成功(pHead在函数结束后并不会发生变化,因为对pHead来说,原型(LNode*pHead)
							  只是直接传参而非间接.*/
{
	/**********************************************************
		按照结点连接次序反转pHead指向的单链表
	//*********************************************************/
	LNode* p,/* p指向将要连接至逆序链表尾的被处理结点*/
		* q;/* q用于保留下一个数据节点(的入口),因为届时p会从原链表断开*/

	   // 1. 断开头结点与单链表中其它数据节点的连接
	p = (*pHead)->link;  // p指向单链表中的第一个数据结点
	(*pHead)->link = 0;  // pHead指向一个空链表

	// 2. 依次把原链表中的数据结点插入到pHead所指链表的表头位置
	while (p != 0) { // 对原链表中的每个数据结点操作(可简写为p)
		q = p->link;  // 保留下一个数据节点(的入口),因为届时p会从原链表断开

	// 把p所指向的结点插入到pHead所指向链表的表头位置，即头结点之后
		p->link = *pHead;
		*pHead = p;/*辅助指针的更新/赋值直接=即可*/

		p = q; 	// p指向下一个数据节点(q就是之前保留的p->link)
	}
	/*内部输出
	printf("由前往后输出当前单链表中的元素\n");
	while (pHead->link)
	{

		printf("%d ", pHead->data);
		pHead = pHead->link;

	}*/

}
//（2）多项式相加
/*
我们可以使用单链表来存储一元多项式。
首先，在节点结构中定义两个数据项，分别用于存放多项式某次项的系数和次数；
然后，按照次数的由低到高，依次把多项式的各个非零项存储到单链表的结点中。

按照上述结点结构，定义两个单链表。
用户输入两个多项式并分别存储到这两个单链表中。

实现算法，对存储在单链表中的两个多项式进行相加，
要求结果存储在一个新单链表中，并且新单链表要求使用原有单链表中的结点单元。
最后，通过依次读取并输出新单链表结点中的数据，打印多项式的求和结果。

对两个多项式进行相加的算法可通过如下函数实现：
*/
/**********************************************************
对存储在单链表poly1和poly2中的两个多项式进行相加，返回存储结果多项式的单链表
/*********************************************************/


/*
（3）综合练习
*/
//同样地，在具体应用程序中，可以使用单链表来存储和管理数据。这里，要求实现一个简单的学生信息管理系统。基本要求如下：
//（1）可对学生对象进行管理，包括插入、删除、查找、统计学生人数；
//（2）使用单链表来存储学生数据；
//（3）由键盘输入学生对象。程序结束时，以文件方式保存学生数据信息；程序执行时，先将文件读入内存。
//其中，学生对象包括学号、姓名、性别、班级等基本信息，可定义如下结构体数据类型来表示学生对象：
//typedef struct {
//	char ID[12];     // 学号
//	char Name[10];  // 姓名
//	int Gender;     // 性别: 0/1 – 男/女
//	char class[15];  // 班级
//}StuInfo;
//为了使用单链表来存储和管理学生数据，可定义如下链表结点类型：
//typedef struct node {
//	StuInfo data;    // 用来存放节点中的学生对象
//	;  // 指向后继节点的指针链：表尾结点的后继结点为空
//}LNode;
//相应地，可实现对应的单链表基本操作，如插入、删除、查找、计算表长等。
